
function dijkstra(graph, source):
    create vertex set Q

    for each vertex v in Graph:
        dist[v] <- INF
        prev[v] <- UNDEFINED
        add v to Q
    dist[source] <- 0

    while Q is not empty:
        u <- vertex in Q with min dist[u]

        remove u from Q

        for each neighbor v of u:
            alt <- dist[u] + length(u, v)
            if alt < dist[v]:
                dist[v] <- alt
                prev[v] <- u
    
    return dist[], prev[]


#邻接矩阵版本

def dijkstra(vermatrix, source):
    Q = list(range(len(vermatrix)))
    
    dist = [99999]*len(vermatrix)
    # 99999 INF
    prev = [-1]*len(vermatrix)
    # -1 UNDEFINED
    dist[source] = 0
    while len(Q) > 0 :
        u = dist.index(min(dist))
        Q.remove(u)
        
        for v in range(len(vermatrix)):
            alt = dist[u] + vermatrix[u][v]
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u

    return dist, prev
